package org.example.myleet.p540;

public class Solution {
    public int singleNonDuplicate(int[] nums) {
        int n = nums.length;
        if (nums.length == 1) {
            return nums[0];
        }
        int l = 0, r = nums.length - 1, m;
        while (l < r) {
            m = (l + r) >>> 1;
            if (m == 0 || m == n - 1 || (nums[m - 1] != nums[m] && nums[m] != nums[m + 1])) {
                return nums[m];
            }
            if ((m & 1) == 1) {
                //m是奇数时
                if (nums[m - 1] == nums[m]) {
                    //nums[m]在一对数的右边，说明左边的全是一对的数，单个的数在右边
                    l = m + 1;
                } else {
                    //nums[m]在一对数的左边，说明单个的数在左边
                    r = m - 1;
                }
            } else {
                //m是偶数时
                if (nums[m] == nums[m + 1]) {
                    //nums[m]在一对数的左边，说明左边的全是一对的数，单个的数在右边
                    l = m + 1;
                } else {
                    //nums[m]在一对数的右边，说明单个的数在左边
                    r = m - 1;
                }
            }
        }
        return nums[l];
    }
}
